/*!  \file  MemoryPool.cpp
 *	  \brief  
 * 
 *   \details   details
 *   \author    Yordan Madzhunkov German Research School for Simulation Sciences GmbH
 *   \version   1.0
 *   \date      07/17/2013 08:36:44 PM
 *   \copyright GNU Public License.
 */
#include <assert.h>
#include <pthread.h>
#include <string.h>
#include "macros.h"
#include "Lock.h"
#include "Queue.h"
//#define MEMORYPOOLLOGGER
class MemoryPoolLogger;
#include "MemoryPool.h"
using namespace std;
#include <iostream>
#include <stdio.h>
typedef int (IDAllocator::*allocFunc)() ;

class IDAllocator  {
public:
	inline void setFresh(const int start_, const int limit) {
		start         = start_;
		recycled      = 0; //here we store all recycled IDs
		nRecycled     = limit;
		limitRecycled = limit;
		setAllocateFresh();
		assert(isFresh());
	};
	inline void setDelocate(const int limit, int * RS storage ) {
		start         = -1;
		recycled      = storage;
		nRecycled     = 0;
		limitRecycled = limit;
		setAllocateRecycled();
	}
	inline void setDelocate() {
		assert( !isFresh()    );
		assert( recycled  != 0);
		assert( nRecycled == 0);
		assert( func      == &IDAllocator::allocateRecycled);
	}
	inline void setAllocate() {
		assert( !isFresh() );
		assert( recycled  != 0);
		assert( nRecycled == limitRecycled);
		assert( func      == &IDAllocator::allocateRecycled);
	}

	//  ----------      -------------      -------------
	//  |  Fresh | -->  |  Delocate | -->  |  Allocate | ---
	//  ----------      -------------      -------------    |
	//                        ^                             |
	//                        |                             |
	//                         -----------------------------

	void setAllocateRecycled() {	func = &IDAllocator::allocateRecycled;	}
	void setAllocateFresh   () {	func = &IDAllocator::allocateFresh   ;	}
	
	bool canAllocate  () const { return nRecycled > 0; }; // OK
	int  getNAllocable() const { return nRecycled    ; }; // OK

	bool canDelocate  () const { return recycled && nRecycled < limitRecycled; }
	int  getNDelocable() const { return limitRecycled - nRecycled; };
	bool isFresh()			const { return start >= 0; };
	int  getLimit     () const { return limitRecycled; };

	void delocate(const int id) { recycled[nRecycled++] = id; };
	int  allocate() { return (this->*func)(); };
	

private:

	int  allocateRecycled () { return recycled[--nRecycled];};
	int  allocateFresh    () { nRecycled--; return start++;};

	int * RS recycled; //here we store all recycled IDs
	allocFunc func;
	int nRecycled, start;
	int limitRecycled;
};
#ifdef MEMORYPOOLLOGGER
struct EventLog {
	int tID; 
	int type;
	int val;
};
class MemoryPoolLogger {
public:
	MemoryPoolLogger(const int size, const int maxThreads) {
		events = new EventLog[size];
		count = 0;
		numThreads = maxThreads;
	}
	virtual ~MemoryPoolLogger() { delArr(events); }
	void log(const int type, const int val, const int tID) {
		lock.lock();
		int res = count++;
		lock.unlock();
		events[res].tID  = tID;
		events[res].type = type;
		events[res].val  = val;
	}
	void printLog() {
		const int w = 20;
		char buf[w + 1]; 
		const char * typeStr[] = {
		"+          %d", // 0 
		"-          %d", // 1
		"deloc fail %d", // 2
		"deloc push %d", // 3
		"deloc pop  %d", // 4
		"alloc push %d", // 5
		"alloc pop  %d"};// 6
		for (int i = 0; i < count ; i++ ) {
			printf("%.5d |", i);
			memset(buf, ' ', w); buf[w] = '\0';
			for (int j = 0; j < events[i].tID; j++)
				printf(buf);
			snprintf(buf, w, typeStr[events[i].type], events[i].val);
			printf(buf);
			memset(buf, ' ', w); buf[w] = '\0';
			for (int j = events[i].tID + 1; j < numThreads; j++)
				printf(buf);
			printf("\n");
		}

	}
private:
	Lock  lock;
	EventLog * events;
	int count;
	int numThreads;

};
#endif
int MemoryPool::getAllocatorID(const IDAllocator * all) const {
	return (all - allAllocators);
}
MemoryPool::MemoryPool(const int maxSize_, const int maxThreads_) {
	blockSize  = 1024;
	maxSize    = maxSize_;
	maxThreads = maxThreads_;

	nBlocks = maxSize/blockSize + (maxSize % blockSize != 0);
	nBlocks = MAX(nBlocks, maxThreads_ * 8  );
	nBlocks = MIN(nBlocks, maxThreads_ * 16 );


	int blockSize = maxSize / nBlocks;
	int rem       = maxSize % nBlocks;
	int usedStorage = 0;

	if (blockSize == 0) {
		blockSize = 1;
		nBlocks = maxSize;
		rem = 0;	
	}


	const int extraLimit  = blockSize + maxSize % blockSize != 0;
	const int extraBlocks = 2 * maxThreads_;
	const int extraSpace  = extraBlocks * extraLimit;

	storage           = new int[maxSize + extraSpace];
	allAllocators     = new IDAllocator[nBlocks * 2 + extraBlocks];
	threadIDAllocator = new ThreadIDAllocator[maxThreads]; 
	allocQueue        = new NoLimitQueue<IDAllocator*>(nBlocks + extraBlocks);
	delocQueue        = new NoLimitQueue<IDAllocator*>(nBlocks + extraBlocks);



	for (int i = 0; i < nBlocks; i++) {
		int limit = blockSize + (i < rem);
		IDAllocator & freshAlloc = allAllocators[i + nBlocks + extraBlocks];
		IDAllocator & deloc      = allAllocators[i];
		assert(getAllocatorID(&deloc) == i);
		assert(getAllocatorID(&freshAlloc) == i + nBlocks + extraBlocks);
	
		freshAlloc.setFresh   (usedStorage, limit);
		assert(freshAlloc.canAllocate());
		deloc.setDelocate(limit, storage + usedStorage);
		assert(deloc.canDelocate());
		usedStorage += limit;

		if ( i < maxThreads) {
			threadIDAllocator[i].alloc = &freshAlloc;			
			threadIDAllocator[i].deloc = &deloc     ;			
		} else {
			allocQueue->pushNoLock(&freshAlloc);
			delocQueue->pushNoLock(&deloc);
		}
	}
	assert(usedStorage == maxSize_); 
	for (int i = nBlocks; i < nBlocks + extraBlocks; i++) {
		int limit = extraLimit; 
		IDAllocator & deloc      = allAllocators[i];
		deloc.setDelocate(limit, storage + usedStorage);
		assert(deloc.canDelocate());
		usedStorage += limit;
		delocQueue->pushNoLock(&deloc);
	}

	if ( false ) {
		cout << endl << "Memory pool info"    << endl;
		cout << "blocks     = " << nBlocks    << endl;
		cout << "block size = " << blockSize  << endl;
		cout << "reminder   = " << rem        << endl;
		cout << "num threads= " << maxThreads << endl;
		cout << "deloc Queue size = " <<  delocQueue->size() << endl;
		cout << "alloc Queue size = " <<  allocQueue->size() << endl;
	}


}
bool MemoryPool::allocate(int & id, const int tID) {
	IDAllocator & allocator = *(threadIDAllocator[tID].alloc);
	if ( allocator.canAllocate() ) {
		id = allocator.allocate();
		return true;
	} else {
		if (!allocator.isFresh()) {
			IDAllocator & delocator = *(threadIDAllocator[tID].deloc);
			if ( delocator.canAllocate() ) {
				id = delocator.allocate();
				threadIDAllocator[tID].swap();
				return true;
			}

			IDAllocator* newAllocator = NULL;
			if (allocQueue->pop(newAllocator)) {
#ifdef MEMORYPOOLLOGGER
				logger->log(6, getAllocatorID(newAllocator), tID);
#endif
				allocator.setDelocate(); // it means do nothing ;) 
				delocQueue->push(&allocator); // there is always space
#ifdef MEMORYPOOLLOGGER
				logger->log(3, getAllocatorID(&allocator), tID);
#endif
				threadIDAllocator[tID].alloc = newAllocator;
				assert(newAllocator->canAllocate());
				id = newAllocator->allocate();	
				return true;
			} else {
				return false;
			}
		} else {
			IDAllocator* newAllocator = NULL;
			if (allocQueue->pop(newAllocator)) {
#ifdef MEMORYPOOLLOGGER
				logger->log(6, getAllocatorID(newAllocator) , tID);
#endif
				threadIDAllocator[tID].alloc = newAllocator;
				assert(newAllocator->canAllocate());
				id = newAllocator->allocate();	
				return true;
			} else 
				return false;
		}
	}
}
bool MemoryPool::delocate(const int id, const int tID) {
	IDAllocator & delocator = *(threadIDAllocator[tID].deloc);
	if ( delocator.canDelocate() ) {
		delocator.delocate(id);
		return true;
	} else {
		IDAllocator* newDelocator = NULL;
		if (delocQueue->pop(newDelocator)) {
#ifdef MEMORYPOOLLOGGER
			int x = (int) newDelocator;
			logger->log(4, getAllocatorID(newDelocator), tID);
#endif
			delocator.setAllocate(); // make it allocatoir
			allocQueue->push(&delocator); // there is always space
#ifdef MEMORYPOOLLOGGER
			logger->log(5, getAllocatorID(&delocator), tID);
#endif
			threadIDAllocator[tID].deloc = newDelocator;
			assert(newDelocator->canDelocate());
			newDelocator->delocate(id);	
			return true;
		} else {
			IDAllocator & allocator = *(threadIDAllocator[tID].alloc);
			if ( allocator.canDelocate() ) {
				allocator.delocate(id);
				return true;
			} else { 
 				return false;
			}
		}
	};
}
MemoryPool::~MemoryPool() {
	delArr(storage);
	delArr(allAllocators);
	delArr(threadIDAllocator);
	delObj(allocQueue);
	delObj(delocQueue);
}
#include "UnitTester.h"
UNITTEST(TestMemoryPool);

TestMemoryPool::TestMemoryPool() {
	setName 				("Test MemoryPool");
	setDescription  	("Test MemoryPool for correct bahaviour & memory allocation");
	setTestAuthor		("Yordan Madzhunkov");
	setDeveloperAuthor("Yordan Madzhunkov");
	setCompileTime    (__DATE__, __TIME__); // each class that inherits this one should also have this line.
};
#include "Stack.h"
struct Params {
	MemoryPool * memoryPool;
#ifdef MEMORYPOOLLOGGER
	MemoryPoolLogger * logger;
#endif
	bool       * checkArray;
	Stack<int> * stack;
	int          id;
	int 			 samples;
	int          nAllocs, nDelocs, nFailAlloc, nFailDeloc, nError;
};
#include <math.h>
#include "RandomGenerator.h"
void * start_routine3(void * arg) {
	Params & p = *(reinterpret_cast<Params *> (arg));
	RandomGenerator * rng = RandomGenerator::defaultGenerator(p.id * 123 + 45);
	p.nAllocs = 0;
	p.nDelocs = 0;
	p.nFailAlloc = 0;
	p.nFailDeloc = 0;
	p.nError  = 0;
	int nSamples = p.samples; 
	int id;
#ifdef MEMORYPOOLLOGGER
	MemoryPoolLogger * logger = p.logger;
#endif
	for (int i = 0; i < nSamples; i++) {
		if (rng->getUniform() < 0.50 ) {
			if (p.memoryPool->allocate(id, p.id) ) {
				if (p.checkArray[id]) {	p.nError++;  };
				p.checkArray[id] = true;
				if (p.stack->push(id) ) {
#ifdef MEMORYPOOLLOGGER
					logger->log(0, id, p.id);
#endif
					p.nAllocs++;
				} else {
					cerr << "Stack doesn't work" << endl;
				}
			} else {
//				cout << "[Thread " << p.id << "]alloc fail" << id << '\n';
				p.nFailAlloc++;
			}
		} else {
			if (p.stack->pop(id) ) {
				if (!p.checkArray[id])	p.nError++;
				if (p.memoryPool->delocate(id, p.id) ) {
					p.checkArray[id] = false;
#ifdef MEMORYPOOLLOGGER
					logger->log(1, id, p.id);
#endif
					p.nDelocs++;
				} else {
#ifdef MEMORYPOOLLOGGER
					logger->log(2, id, p.id);
#endif
					p.stack->push(id);
					p.nFailDeloc++;
				}
			}
		}
	}
/* 	while (p.stack->pop(id) ) {
		if (!p.checkArray[id])	p.nError++;
		if (p.memoryPool->delocate(id, p.id) ) {
			p.checkArray[id] = false;
#ifdef MEMORYPOOLLOGGER
			logger->log(1, id, p.id);
#endif
			p.nDelocs++;
		} else {
#ifdef MEMORYPOOLLOGGER
			logger->log(2, id, p.id);
#endif
			p.stack->push(id);
			p.nFailDeloc++;
		}
	}
*/
	delObj(rng);
	return NULL;	
}
bool TestMemoryPool::test() const {
	const int nThreads  = 2;
	const int blockSize = 4;
	const int size      = 8 * blockSize * nThreads;
	const int nSamples  = 100 * nThreads * size;

	Params p[nThreads];
	MemoryPool * memoryPool = new MemoryPool(size, nThreads);
	bool       * checkArray = new bool[size]; 
	Stack<int> * stack      = new Stack<int>(size + 4);


#ifdef MEMORYPOOLLOGGER
	MemoryPoolLogger * logger = new MemoryPoolLogger(2 * nSamples * nThreads, nThreads);
	memoryPool->logger = logger;
#endif
	memset(checkArray, 0, size * sizeof(checkArray[0]));
	pthread_t threadIDs[nThreads];

	for (int i = 0; i < nThreads; i++) {
		p[i].memoryPool = memoryPool;
		p[i].checkArray = checkArray;
		p[i].id         = i;
		p[i].stack      = stack;
#ifdef MEMORYPOOLLOGGER
		p[i].logger     = logger;
#endif
		p[i].samples    = nSamples;
	}

	for (int i = 1; i < nThreads; i++) {
		int info = pthread_create(&threadIDs[i], NULL, &start_routine3, &p[i]);
		assert(info == 0);
	}
	// use the current thread as well
	start_routine3(&p[0]);
	// join all theads	
	for (int i = 1; i < nThreads; i++) if (threadIDs[i]) {
		void * exitPtr = NULL;
		pthread_join(threadIDs[i], &exitPtr);	
		threadIDs[i] = 0;		
	}
	bool res = false;
#ifdef MEMORYPOOLLOGGER
	logger->printLog();
#endif
	for (int i = 0; i < nThreads; i++) {
		cout << "ThreadID    = "  << p[i].id;
		cout << " errors     = "  << p[i].nError;
		cout << " nFailAlloc = "  << p[i].nFailAlloc;
		cout << " nFailDeloc = "  << p[i].nFailDeloc << endl;
		res &= p[i].nError == 0 && p[i].nFailDeloc == 0;
	}
	delObj(stack);
	delObj(memoryPool);
#ifdef MEMORYPOOLLOGGER
	delObj(logger);
#endif
	delArr(checkArray);
	return res;
}
TestMemoryPool testMemoryPool;
